/*
 * Copyright (C) 2009-2012  Paulo Cesar Pereira de Andrade.
 *
 * This is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * Authors:
 *	Paulo Cesar Pereira de Andrade
 */

#include "exl.h"

#define get_mpz()		(empz_t)ssa_vector->v.ptr[ssa_vector->offset++]
#if __WORDSIZE == 64
#  define check_ssa_vector_offset()					\
    assert((eint32_t)ssa_vector->offset == ssa_vector->offset)
#else
#  define check_ssa_vector_offset()					\
    do ; while (0)
#endif

/*
 * Prototypes
 */
static void
ssa1_ast(east_t *ast, empz_t set);

static void
ssa1_ast_change(east_t *ast, empz_t set);

static void
ssa1_ast_vector_change(east_t *ast, empz_t set);

static void
ssa1_ast_set(east_t *ast, empz_t set);

static void
ssa1_ast_stat(east_t *ast, empz_t set);

static void
ssa1_ast_decl(east_t *decl, empz_t set);

static void
ssa1_ast_call(empz_t set);

static void
ssa2_ast(east_t *ast, empz_t set);

static east_t *
ssa2_ast_set(east_t *ast, empz_t set);

static void
ssa2_ast_change(east_t *ast);

static void
ssa2_ast_postchange(east_t *ast);

static void
ssa2_ast_stat(east_t *ast, empz_t set);

static void
ssa2_ast_decl(east_t *decl, empz_t set);

static void
ssa2_call(void);

static void
ssa_ast_set(east_t *ast);

static void
ssa_set(evalue_t *value);

static void
ssa_ast_use(east_t *ast);

static void
ssa_use(evalue_t *value);

static void
ssa_inc(evalue_t *value);

static void
ssa_merge(empz_t set, empz_t rset);

static empz_t
new_mpz(void);

/*
 * Initialization
 */
static evector_t	*ssa_value;
static evector_t	*ssa_vector;

/*
 * Implementation
 */
void
init_ssa(void)
{
    eadd_root((eobject_t *)&ssa_value);
    enew_vector((eobject_t *)&ssa_value, t_void, 16);
    eadd_root((eobject_t *)&ssa_vector);
    enew_vector((eobject_t *)&ssa_vector, t_void, 16);
}

void
finish_ssa(void)
{
    erem_root((eobject_t *)&ssa_value);
    erem_root((eobject_t *)&ssa_vector);
}

void
essa(east_t *ast)
{
    empz_t		 set;
    ehash_t		*hash;
    east_t		*label;
    eentry_t		*entry;
    evalue_t		*value;
    eword_t		 offset;
    esymbol_t		*symbol;
    evector_t		*vector;

    ssa_value->offset = 0;
    vector = current_function->value_vector;
    assert(current_namespace == current_function->namespace);
    for (offset = 0; offset < vector->offset; offset++) {
	value = vector->v.ptr[offset];
	assert(value->offset >= 0);
	if (esymbol_p(value->name)) {
	    symbol = value->name;
	    if (symbol->namespace == current_namespace &&
		(symbol->tag->type == tag_basic ||
		 symbol->tag->type == tag_auto))
		continue;
	}
	if (ssa_value->offset >= ssa_value->length)
	    erenew_vector(ssa_value, ssa_value->length + 16);
	ssa_value->v.ptr[ssa_value->offset++] = value;
    }

    ssa_vector->offset = 0;
    set = new_mpz();

    hash = current_function->label_table;
    for (offset = 0; offset < hash->size; offset++) {
	for (entry = hash->entries[offset]; entry; entry = entry->next) {
	    label = entry->value;
	    label->t.value = new_mpz();
	}
    }
    offset = hash->count + 1;

    /*   Must do two passes to record state in labels to properly handle
     * backwards goto. ssa1_xyz new_mpz calls must match exactly ssa2_xyz
     * get_mpz calls. */

    /*   Pass1: update bitmap of values modified and record multiple paths. */
    ssa_vector->offset = offset;
    ssa1_ast_stat(ast, set);

    /*   Pass2: merge bitmaps, and attach a unique symbolic indentifier to
     * symbol references. */
    mpz_set_ui(set, 0);
    ssa_vector->offset = offset;
    ssa2_ast_stat(ast, set);
}

void
enew_value(eobject_t *pointer, eobject_t name, eint32_t offset)
{
    evalue_t		*value;

    enew_object(pointer, t_value, sizeof(evalue_t));
    value = *pointer;
    value->name = name;
    value->offset = offset;
}

static void
ssa1_ast(east_t *ast, empz_t set)
{
    empz_t		 lset;
    empz_t		 rset;
    east_t		*label;

    switch (ast->token) {
	case tok_set:		case tok_andset:
	case tok_orset:		case tok_xorset:
	case tok_mul2set:	case tok_div2set:
	case tok_shlset:	case tok_shrset:
	case tok_addset:	case tok_subset:
	case tok_mulset:	case tok_divset:
	case tok_trunc2set:	case tok_remset:
	    ssa1_ast_set(ast->l.ast, set);
	    ssa1_ast(ast->r.ast, set);
	    break;
	case tok_inc:		case tok_dec:
	case tok_postinc:	case tok_postdec:
	    ssa1_ast_set(ast->l.ast, set);
	    break;
	case tok_plus:		case tok_neg:
	case tok_not:		case tok_com:
	case tok_dot:
	    ssa1_ast(ast->l.ast, set);
	    break;
	case tok_ne:		case tok_lt:
	case tok_le:		case tok_eq:
	case tok_ge:		case tok_gt:
	case tok_and:		case tok_or:
	case tok_xor:		case tok_mul2:
	case tok_div2:		case tok_shl:
	case tok_shr:		case tok_add:
	case tok_sub:		case tok_mul:
	case tok_div:		case tok_trunc2:
	case tok_rem:
	case tok_vector:
	    ssa1_ast(ast->l.ast, set);
	    ssa1_ast(ast->r.ast, set);
	    break;
	case tok_andand:	case tok_oror:
	    ssa1_ast(ast->l.ast, set);
	    lset = new_mpz();
	    ssa1_ast(ast->r.ast, lset);
	    break;
	case tok_question:
	    ssa1_ast(ast->t.ast, set);
	    check_ssa_vector_offset();
	    ast->code = ssa_vector->offset;
	    lset = new_mpz();
	    ssa1_ast_stat(ast->l.ast, lset);
	    rset = new_mpz();
	    ssa1_ast_stat(ast->r.ast, rset);
	    break;
	case tok_if:
	    ssa1_ast_stat(ast->t.ast, set);
	    check_ssa_vector_offset();
	    ast->code = ssa_vector->offset;
	    lset = new_mpz();
	    ssa1_ast_stat(ast->l.ast, lset);
	    check_ssa_vector_offset();
	    rset = new_mpz();
	    ssa1_ast_stat(ast->r.ast, rset);
	    break;
	case tok_for:
	    /* init */
	    ssa1_ast_stat(ast->l.ast, set);
	    check_ssa_vector_offset();
	    ast->code = ssa_vector->offset;
	    lset = new_mpz();
	    ssa1_ast_stat(ast->t.ast, lset);	/* test */
	    ssa1_ast_stat(ast->c.ast, lset);	/* body */
	    ssa1_ast_stat(ast->r.ast, lset);	/* incr */
	    break;
	case tok_while:
	    check_ssa_vector_offset();
	    ast->code = ssa_vector->offset;
	    lset = new_mpz();
	    ssa1_ast_stat(ast->t.ast, lset);	/* test */
	    ssa1_ast_stat(ast->c.ast, lset);	/* body */
	    break;
	case tok_do:
	    check_ssa_vector_offset();
	    ast->code = ssa_vector->offset;
	    lset = new_mpz();
	    ssa1_ast_stat(ast->c.ast, lset);	/* body */
	    ssa1_ast_stat(ast->t.ast, lset);	/* test */
	    break;
	case tok_switch:
	    ssa1_ast_stat(ast->t.ast, set);
	    check_ssa_vector_offset();
	    ast->code = ssa_vector->offset;
	    lset = new_mpz();
	    mpz_set(lset, set);
	    /*   Will copy lset as set state after case/default. */
	    ssa1_ast_stat(ast->c.ast, set);
	    /*   Code after case/default need to start with this set,
	     * that is, to ensure references to symbol set in one case
	     * do not map to the same identifier in another case. */
	    mpz_ior(lset, lset, set);
	    break;
	case tok_case:		case tok_default:
	    label = ast->c.ast;
	    lset = ssa_vector->v.ptr[label->code];
	    rset = new_mpz();
	    mpz_set(rset, lset);
	    ast->t.value = rset;
	    break;
	case tok_list:		case tok_stat:
	case tok_code:		case tok_data:
	    ssa1_ast_stat(ast->l.ast, set);
	    break;
	case tok_decl:
	    ssa1_ast(ast->l.ast, set);
	    ssa1_ast_decl(ast->r.ast, set);
	    break;
	case tok_goto:
	    label = ast->c.ast;
	    lset = label->t.value;
	    mpz_ior(lset, lset, set);
	    break;
	case tok_return:
	    if (ast->l.value)
		ssa1_ast(ast->l.ast, set);
	    break;
	case tok_call:
	    ssa1_ast_stat(ast->r.ast, set);
	    ssa1_ast_call(set);
	    break;
	case tok_type:		case tok_symbol:
	case tok_number:	case tok_string:
	case tok_label:		case tok_break:
	case tok_continue:	case tok_class:
	case tok_function:
	    break;
	default:
#if DEBUG
	    eparse_warn(ast,
			"ssa1: not handling %s", etoken_to_charp(ast->token));
#endif
	    break;
    }
}

static void
ssa1_ast_change(east_t *ast, empz_t set)
{
    evalue_t		*value;

    value = ast->c.value;
    mpz_setbit(set, value->offset);
}

static void
ssa1_ast_vector_change(east_t *ast, empz_t set)
{
    evalue_t		*entry;
    evalue_t		*value;
    eword_t		 offset;

    assert(ast->token == tok_vector);
    value = ast->c.value;
    if (value->parent) {
	mpz_setbit(set, value->offset);
	mpz_setbit(set, value->parent->offset);
    }
    else if (value->alias) {
	for (offset = 0; offset < value->alias->offset; offset++) {
	    entry = value->alias->v.ptr[offset];
	    mpz_setbit(set, entry->offset);
	}
    }
}

static void
ssa1_ast_set(east_t *ast, empz_t set)
{
    switch (ast->token) {
	case tok_symbol:
	    ssa1_ast_change(ast, set);
	    break;
	case tok_dot:
	    ssa1_ast_change(ast->r.ast, set);
	    break;
	case tok_vector:
	    ssa1_ast_vector_change(ast, set);
	    break;
	default:
	    ssa1_ast(ast, set);
	    break;
    }
}

static void
ssa1_ast_stat(east_t *ast, empz_t set)
{
    for (; ast; ast = ast->next)
	ssa1_ast(ast, set);
}

static void
ssa1_ast_decl(east_t *decl, empz_t set)
{
    east_t		*ast;
    east_t		*list;

    for (list = decl; list; list = list->next) {
	ast = list;
	switch (ast->token) {
	    case tok_symbol:
		break;
	    case tok_set:	case tok_vector:	case tok_proto:
		ssa1_ast(ast->r.ast, set);
		for (ast = ast->l.ast;
		     ast->token != tok_symbol; ast = ast->l.ast)
		    ;
		break;
	    default:
		abort();
	}
    }
}

static void
ssa1_ast_call(empz_t set)
{
    evalue_t		*value;
    eword_t		 offset;

    for (offset = 0; offset < ssa_value->offset; offset++) {
	value = ssa_value->v.ptr[offset];
	mpz_setbit(set, value->offset);
    }
}

static void
ssa2_ast(east_t *ast, empz_t set)
{
    empz_t		 lset;
    empz_t		 rset;
    east_t		*temp;
    eword_t		 index;

    switch (ast->token) {
	case tok_set:		case tok_andset:
	case tok_orset:		case tok_xorset:
	case tok_mul2set:	case tok_div2set:
	case tok_shlset:	case tok_shrset:
	case tok_addset:	case tok_subset:
	case tok_mulset:	case tok_divset:
	case tok_trunc2set:	case tok_remset:
	    temp = ssa2_ast_set(ast->l.ast, set);
	    ssa2_ast(ast->r.ast, set);
	    if (temp)
		ssa2_ast_change(temp);
	    break;
	case tok_inc:		case tok_dec:
	    if ((temp = ssa2_ast_set(ast->l.ast, set)))
		ssa2_ast_change(temp);
	    break;
	case tok_postinc:	case tok_postdec:
	    /* FIXME This may not be correct in some special context,
	     * where it would be better done to just handle post{inc,dec}
	     * as {inc,dec}. */
	    if ((temp = ssa2_ast_set(ast->l.ast, set)))
		ssa2_ast_postchange(temp);
	    break;
	case tok_plus:		case tok_neg:
	case tok_not:		case tok_com:
	    ssa2_ast(ast->l.ast, set);
	    break;
	case tok_dot:
	    if (ast->l.ast->token == tok_symbol)
		ssa_ast_use(ast->l.ast);
	    else
		ssa2_ast(ast->l.ast, set);
	    ssa_ast_use(ast->r.ast);
	    break;
	case tok_ne:		case tok_lt:
	case tok_le:		case tok_eq:
	case tok_ge:		case tok_gt:
	case tok_and:		case tok_or:
	case tok_xor:		case tok_mul2:
	case tok_div2:		case tok_shl:
	case tok_shr:		case tok_add:
	case tok_sub:		case tok_mul:
	case tok_div:		case tok_trunc2:
	case tok_rem:
	case tok_vector:
	    ssa2_ast(ast->l.ast, set);
	    ssa2_ast(ast->r.ast, set);
	    break;
	case tok_andand:	case tok_oror:
	    ssa2_ast(ast->l.ast, set);
	    lset = get_mpz();
	    ssa2_ast(ast->r.ast, lset);
	    ssa_merge(set, lset);
	    break;
	case tok_question:
	    ssa2_ast(ast->t.ast, set);
	    assert(ast->code == ssa_vector->offset);
	    lset = get_mpz();
	    ssa2_ast_stat(ast->l.ast, lset);
	    rset = get_mpz();
	    ssa2_ast_stat(ast->r.ast, rset);
	    ssa_merge(set, lset);
	    ssa_merge(set, rset);
	    break;
	case tok_if:
	    ssa2_ast_stat(ast->t.ast, set);
	    assert(ast->code == ssa_vector->offset);
	    lset = get_mpz();
	    ssa2_ast_stat(ast->l.ast, lset);
	    rset = get_mpz();
	    ssa2_ast_stat(ast->r.ast, rset);
	    ssa_merge(set, lset);
	    ssa_merge(set, rset);
	    break;
	case tok_for:
	    ssa2_ast_stat(ast->l.ast, set);	/* init */
	    assert(ast->code == ssa_vector->offset);
	    lset = get_mpz();
	    ssa_merge(lset, lset);		/* loop */
	    ssa2_ast_stat(ast->t.ast, lset);	/* test */
	    ssa2_ast_stat(ast->c.ast, lset);	/* body */
	    ssa2_ast_stat(ast->r.ast, lset);	/* incr */
	    ssa_merge(set, lset);
	    break;
	case tok_while:
	    assert(ast->code == ssa_vector->offset);
	    lset = get_mpz();
	    ssa_merge(lset, lset);		/* loop */
	    ssa2_ast_stat(ast->t.ast, lset);	/* test */
	    ssa2_ast_stat(ast->c.ast, lset);	/* body */
	    ssa_merge(set, lset);
	    break;
	case tok_do:
	    assert(ast->code == ssa_vector->offset);
	    lset = get_mpz();
	    ssa_merge(lset, lset);		/* loop */
	    ssa2_ast_stat(ast->c.ast, lset);	/* body */
	    ssa2_ast_stat(ast->t.ast, lset);	/* test */
	    ssa_merge(set, lset);
	    break;
	case tok_switch:
	    ssa2_ast_stat(ast->t.ast, set);
	    assert(ast->code == ssa_vector->offset);
	    lset = get_mpz();
	    ssa2_ast_stat(ast->c.ast, lset);
	    ssa_merge(set, lset);
	    break;
	case tok_break:		case tok_continue:
	    /*   Conditional code below break or continue. */
	    temp = ast->c.ast;
	    for (index = ssa_vector->offset - 1; index >= temp->code; index--) {
		lset = ssa_vector->v.ptr[index];
		ssa_merge(set, lset);
	    }
	    break;
	case tok_list:		case tok_stat:
	case tok_code:		case tok_data:
	    ssa2_ast_stat(ast->l.ast, set);
	    break;
	case tok_decl:
	    ssa2_ast(ast->l.ast, set);
	    ssa2_ast_decl(ast->r.ast, set);
	    break;
	case tok_symbol:
	    ssa_ast_use(ast);
	    break;
	case tok_case:		case tok_default:
	    lset = get_mpz();
	    assert(lset == ast->t.value);
	    ssa_merge(set, lset);
	    ast->t.ast = null;
	    /*   Note that loads of symbols are not in the same flow
	     * as another case/default entry. */
	    temp = ast->c.ast;
	    lset = ssa_vector->v.ptr[temp->code];
	    ssa_merge(set, lset);
	    break;
	case tok_label:
	    lset = ast->t.value;
	    ssa_merge(set, lset);
	    ast->t.ast = null;
	    break;
	case tok_return:
	    if (ast->l.value)
		ssa2_ast(ast->l.ast, set);
	    break;
	case tok_call:
	    ssa2_ast_stat(ast->r.ast, set);
	    ssa2_call();
	    break;
	case tok_type:		case tok_number:
	case tok_string:	case tok_goto:
	case tok_class:		case tok_function:
	    break;
	default:
#if DEBUG
	    eparse_warn(ast,
			"ssa2: not handling %s", etoken_to_charp(ast->token));
#endif
	    break;
    }
}

static east_t *
ssa2_ast_set(east_t *ast, empz_t set)
{
    switch (ast->token) {
	case tok_symbol:
	    break;
	case tok_dot:
	    ssa2_ast(ast->l.ast, set);
	    ast = ast->r.ast;
	    break;
	case tok_vector:
	    ssa2_ast_stat(ast->r.ast, set);
	    break;
	default:
	    ssa2_ast(ast, set);
	    ast = null;
	    break;
    }

    return (ast);
}

static void
ssa2_ast_change(east_t *ast)
{
    evalue_t		*value;
    eword_t		 offset;

    /*  Force "version" increase of all vector elements that may alias. */
    if (ast->token == tok_vector) {
	value = ast->c.value;
	if (value->parent) {
	    ssa_ast_set(ast);
	    ssa_inc(value->parent);
	}
	else {
	    if (value->alias) {
		for (offset = 0; offset < value->alias->offset; offset++)
		    ssa_inc(value->alias->v.ptr[offset]);
	    }
	    ssa_ast_set(ast);
	}
    }
    else
	ssa_ast_set(ast);
}

static void
ssa2_ast_postchange(east_t *ast)
{
    evalue_t		*value;
    eword_t		 offset;

    value = ast->c.value;
    ssa_ast_use(ast);
    ssa_inc(value);
    if (value->parent)
	ssa_inc(value->parent);
    else if (value->alias) {
	for (offset = 0; offset < value->alias->offset; offset++)
	    ssa_inc(value->alias->v.ptr[offset]);
    }
}

static void
ssa2_ast_stat(east_t *ast, empz_t set)
{
    for (; ast; ast = ast->next)
	ssa2_ast(ast, set);
}

static void
ssa2_ast_decl(east_t *decl, empz_t set)
{
    east_t		*ast;
    east_t		*list;

    for (list = decl; list; list = list->next) {
	ast = list;
	switch (ast->token) {
	    case tok_symbol:
		ssa_ast_use(ast);
		break;
	    case tok_set:	case tok_vector:	case tok_proto:
		ssa2_ast(ast->r.ast, set);
		for (ast = ast->l.ast;
		     ast->token != tok_symbol; ast = ast->l.ast)
		    ;
		ssa_ast_use(ast);
		break;
	    default:
		abort();
	}
    }
}

static void
ssa2_call(void)
{
    eword_t		offset;

    for (offset = 0; offset < ssa_value->offset; offset++)
	ssa_inc(ssa_value->v.ptr[offset]);
}

static void
ssa_ast_set(east_t *ast)
{
    evalue_t		*value;

    assert(ast->token == tok_symbol || ast->token == tok_vector);
    value = ast->c.value;
    ssa_set(value);
    ast->code = value->version;
}

static void
ssa_set(evalue_t *value)
{
    if (value->version & 0x80000000)
	value->version &= 0x7fffffff;
    else {
	++value->version;
	assert(!(value->version & 0x80000000));
    }
}

static void
ssa_ast_use(east_t *ast)
{
    evalue_t		*value;

    assert(ast->token == tok_symbol || ast->token == tok_vector);
    value = ast->c.value;
    ssa_use(value);
    ast->code = value->version;
}

static void
ssa_use(evalue_t *value)
{
    if (value->version & 0x80000000)
	value->version &= 0x7fffffff;
}

static void
ssa_inc(evalue_t *value)
{
    if (!(value->version & 0x80000000)) {
	++value->version;
	assert(!(value->version & 0x80000000));
	value->version |= 0x80000000;
    }
}

static void
ssa_merge(empz_t set, empz_t rset)
{
    unsigned long	 bit;
    evector_t		*vector;

    mpz_ior(set, set, rset);
    vector = current_function->value_vector;
    for (bit = mpz_scan1(set, 0); bit != ULONG_MAX; bit = mpz_scan1(set, bit)) {
	ssa_inc(vector->v.ptr[bit]);
	++bit;
    }
}

static empz_t
new_mpz(void)
{
    empz_t		mpz;

    if (ssa_vector->offset >= ssa_vector->length)
	erenew_vector(ssa_vector, ssa_vector->offset + 16);
    if (ssa_vector->v.ptr[ssa_vector->offset] == null)
	eget_mpz(ssa_vector->v.ptr + ssa_vector->offset);
    mpz = ssa_vector->v.ptr[ssa_vector->offset++];
    mpz_set_ui(mpz, 0);

    return (mpz);
}
